home *** CD-ROM | disk | FTP | other *** search
/ AP Professional Graphics CD-ROM Library / AP Professional Graphics CD-ROM Library.iso / pc / unix / appendix / gemsi / aaplyscn.c next >
Encoding:
C/C++ Source or Header  |  1993-08-25  |  7.4 KB  |  249 lines
  1. /* 
  2. Fast Anti-Aliasing Polygon Scan Conversion
  3. by Jack Morrison
  4. from "Graphics Gems", Academic Press, 1990
  5.  
  6. user provides screenX(), vLerp(), and renderPixel() routines.
  7. */
  8.  
  9. /*
  10. * Anti-aliased polygon scan conversion by Jack Morrison
  11. *
  12. * This code renders a polygon, computing subpixel coverage at
  13. * 8 times Y and 16 times X display resolution for anti-aliasing.
  14. * One optimization left out for clarity is the use of incremental
  15. * interpolations. X coordinate interpolation in particular can be
  16. * with integers. See Dan Field's article in ACM Transactions on
  17. * Graphics, January 1985 for a fast incremental interpolator.
  18. */
  19. #include <math.h>
  20. #include "GraphicsGems.h"
  21.  
  22. #define    SUBYRES    8        /* subpixel Y resolution per scanline */
  23. #define    SUBXRES    16        /* subpixel X resolution per pixel */
  24. #define    MAX_AREA    (SUBYRES*SUBXRES)
  25. #define    MODRES(y)    ((y) & 7)        /*subpixel Y modulo */
  26. #define MAX_X    0x7FFF    /* subpixel X beyond right edge */
  27.  
  28. typedef struct SurfaceStruct {  /* object shading surface info */
  29.     int    red, green, blue;           /* color components */
  30.     } Surface;
  31. /*
  32. * In  real life, SurfaceStruct will contain many more parameters as
  33. * required by the shading and rendering programs, such as diffuse
  34. * and specular factors, texture information, transparency, etc.
  35. */
  36.  
  37. typedef struct VertexStruct    {    /* polygon vertex */
  38.     Vector3    model, world,        /* geometric information */
  39.             normal, image;
  40.     int y;                    /* subpixel display coordinate */
  41.     } Vertex;
  42.  
  43. Vertex *Vleft, *VnextLeft;        /* current left edge */
  44. Vertex *Vright, *VnextRight;    /* current right edge */
  45.  
  46. struct    SubPixel  {            /* subpixel extents for scanline */
  47.     int xLeft, xRight;
  48.     } sp[SUBYRES];
  49.  
  50. int    xLmin, xLmax;        /* subpixel x extremes for scanline */
  51. int    xRmax, xRmin;        /* (for optimization shortcut) */
  52.  
  53. /* Compute sub-pixel x coordinate for vertex */
  54. extern int screenX(/* Vertex *v */);
  55.  
  56. /* Interpolate vertex information */
  57. extern void vLerp(/* double alpha, Vertex *Va, *Vb, *Vout */);
  58.  
  59. /* Render polygon for one pixel, given coverage area */
  60. /*  and bitmask */
  61. extern void renderPixel(/* int x, y, Vertex *V,
  62.                         int area, unsigned mask[], 
  63.                         Surface *object */);
  64.  
  65. /*
  66.  * Render shaded polygon
  67.  */
  68. drawPolygon(polygon, numVertex, object)
  69.     Vertex    polygon[];        /*clockwise clipped vertex list */
  70.     int    numVertex;            /*number of vertices in polygon */
  71.  
  72.     Surface *object;            /* shading parms for this object */
  73. {
  74.     Vertex *endPoly;            /* end of polygon vertex list */
  75.     Vertex VscanLeft, VscanRight;    /* interpolated vertices */                                 /* at scanline */
  76.     double aLeft, aRight;            /* interpolation ratios */
  77.     struct SubPixel *sp_ptr;        /* current subpixel info */
  78.     int xLeft, xNextLeft;            /* subpixel coordinates for */
  79.     int  xRight, xNextRight;        /* active polygon edges */
  80.     int i,y;                        
  81.  
  82. /* find vertex with minimum y (display coordinate) */
  83. Vleft = polygon;
  84. for  (i=1; i<numVertex; i++)
  85.     if  (polygon[i].y < Vleft->y)
  86.         Vleft = &polygon[i];
  87. endPoly = &polygon[numVertex-1];
  88.  
  89. /* initialize scanning edges */
  90. Vright = VnextRight = VnextLeft = Vleft;
  91.  
  92. /* prepare bottom of initial scanline - no coverage by polygon */
  93. for (i=0; i<SUBYRES; i++)
  94.     sp[i].xLeft = sp[i].xRight = -1;
  95. xLmin = xRmin = MAX_X;
  96. xLmax = xRmax = -1;
  97.  
  98. /* scan convert for each subpixel from bottom to top */
  99. for (y=Vleft->y; ; y++)    {
  100.  
  101.     while (y == VnextLeft->y)    {    /* reached next left vertex */
  102.         VnextLeft = (Vleft=VnextLeft) + 1;     /* advance */
  103.         if (VnextLeft > endPoly)            /* (wraparound) */
  104.             VnextLeft = polygon;
  105.         if (VnextLeft == Vright)    /* all y's same?  */
  106.             return;                /* (null polygon) */ 
  107.         xLeft = screenX(Vleft);
  108.         xNextLeft = screenX(VnextLeft);
  109.     }
  110.  
  111.     while (y == VnextRight->y)  { /*reached next right vertex */
  112.         VnextRight = (Vright=VnextRight) -1;
  113.         if (VnextRight < polygon)            /* (wraparound) */
  114.             VnextRight = endPoly;
  115.         xRight = screenX(Vright);
  116.         xNextRight = screenX(VnextRight);
  117.     }
  118.  
  119.     if (y>VnextLeft->y || y>VnextRight->y)    {
  120.                 /* done, mark uncovered part of last scanline */
  121.         for (; MODRES(y); y++)
  122.             sp[MODRES(y)].xLeft = sp[MODRES(y)].xRight = -1;
  123.         renderScanline(Vleft, Vright, y/SUBYRES, object);
  124.         return;
  125.     }
  126.  
  127. /*
  128.  * Interpolate sub-pixel x endpoints at this y,
  129.  * and update extremes for pixel coherence optimization
  130.  */
  131.     
  132.     sp_ptr = &sp[MODRES(y)];
  133.     aLeft = (double)(y - Vleft->y) / (VnextLeft->y - Vleft->y);
  134.     sp_ptr->xLeft = LERP(aLeft, xLeft, xNextLeft);
  135.     if (sp_ptr->xLeft < xLmin)
  136.         xLmin = sp_ptr->xLeft;
  137.     if (sp_ptr->xLeft > xLmax)
  138.         xLmax = sp_ptr->xLeft;
  139.  
  140.     aRight = (double)(y - Vright->y) / (VnextRight->y 
  141.                     - Vright->y);
  142.     sp_ptr->xRight = LERP(aRight, xRight, xNextRight);
  143.     if (sp_ptr->xRight < xRmin)
  144.         xRmin = sp_ptr->xRight;
  145.     if (sp_ptr->xRight > xRmax)
  146.         xRmax = sp_ptr->xRight;
  147.  
  148.     if (MODRES(y) == SUBYRES-1)    {    /* end of scanline */
  149.             /* interpolate edges to this scanline */
  150.         vLerp(aLeft, Vleft, VnextLeft, &VscanLeft);
  151.         vLerp(aRight, Vright, VnextRight, &VscanRight);
  152.         renderScanline(&VscanLeft, &VscanRight, y/SUBYRES, object);
  153.         xLmin = xRmin = MAX_X;         /* reset extremes */
  154.         xLmax = xRmax = -1;
  155.     }
  156.   }
  157. }
  158.  
  159. /*
  160.  * Render one scanline of polygon
  161.  */
  162.  
  163. renderScanline(Vl, Vr, y, object)
  164.     Vertex *Vl, *Vr;     /* polygon vertices interpolated */
  165.                     /* at scanline */   
  166.     int y;            /* scanline coordinate */
  167.     Surface *object;    /* shading parms for this object */
  168. {
  169.     Vertex Vpixel;    /*object info interpolated at one pixel */
  170.     unsigned mask[SUBYRES];    /*pixel coverage bitmask */
  171.     int x;            /* leftmost subpixel of current pixel */
  172.  
  173.     for (x=SUBXRES*floor((double)(xLmin/SUBXRES)); x<=xRmax; x+=SUBXRES) {
  174.         vLerp((double)(x-xLmin)/(xRmax-xLmin), Vl, Vr, &Vpixel);
  175.         computePixelMask(x, mask);
  176.         renderPixel(x/SUBXRES, y, &Vpixel,
  177.                     /*computePixel*/Coverage(x), mask, object);
  178.     }
  179. }
  180.  
  181. /*
  182.  * Compute number of subpixels covered by polygon at current pixel
  183. */
  184. /*computePixel*/Coverage(x)
  185.     int x;            /* left subpixel of pixel */
  186. {
  187.     int  area;            /* total covered area */
  188.     int partialArea;      /* covered area for current subpixel y */
  189.     int xr = x+SUBXRES-1;    /*right subpixel of pixel */
  190.     int y;
  191.  
  192.     /* shortcut for common case of fully covered pixel */
  193.     if (x>xLmax && x<xRmin)
  194.         return MAX_AREA;
  195.     
  196.     for (area=y=0; y<SUBYRES; y++) {
  197.         partialArea = MIN(sp[y].xRight, xr)
  198.              - MAX(sp[y].xLeft, x) + 1;
  199.         if (partialArea > 0)
  200.             area += partialArea;
  201.     }
  202.     return area;
  203. }
  204.  
  205. /* Compute bitmask indicating which subpixels are covered by 
  206.  * polygon at current pixel. (Not all hidden-surface methods
  207.  * need this mask. )
  208. */
  209. computePixelMask(x, mask)
  210.     int x;            /* left subpixel of pixel */
  211.     unsigned mask[];    /* output bitmask */
  212. {
  213.     static unsigned leftMaskTable[] =
  214.         { 0xFFFF, 0x7FFF, 0x3FFF, 0x1FFF, 0x0FFF, 0x07FF, 0x03FF,
  215.           0x01FF, 0x00FF, 0x007F, 0x003F, 0x001F, 0x000F, 0x0007,
  216.           0x0003, 0x0001  };
  217.     static unsigned rightMaskTable[] = 
  218.         { 0x8000, 0xC000, 0xE000, 0xF000, 0xF800, 0xFC00, 
  219.           0xFE00, 0xFF00, 0xFF80, 0xFFC0, 0xFFE0, 0xFFF0,
  220.           0xFFF8, 0xFFFC, 0xFFFE, 0xFFFF   };
  221.     unsigned leftMask, rightMask;         /* partial masks */
  222.     int xr = x+SUBXRES-1;            /* right subpixel of pixel */
  223.     int y;
  224.  
  225. /* shortcut for common case of fully covered pixel */
  226.     if (x>xLmax && x<xRmin)     {
  227.         for (y=0; y<SUBYRES; y++)
  228.             mask[y] = 0xFFFF;
  229.     } else     {
  230.         for (y=0; y<SUBYRES; y++)    {
  231.             if (sp[y].xLeft < x)     /* completely left of pixel*/
  232.                 leftMask = 0xFFFF;
  233.             else if (sp[y].xLeft > xr)  /* completely right */    
  234.                 leftMask = 0;
  235.             else
  236.                 leftMask = leftMaskTable[sp[y].xLeft -x];
  237.  
  238.             if (sp[y].xRight > xr)      /* completely  */
  239.                             /* right of pixel*/
  240.                 rightMask = 0xFFFF;
  241.             else if (sp[y].xRight < x)    /*completely left */
  242.                 rightMask = 0;
  243.             else
  244.                 rightMask = rightMaskTable[sp[y].xRight -x];
  245.             mask[y] = leftMask & rightMask;
  246.         }
  247.     }
  248. }
  249.